package com.data_structure_test.queue;

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

/**
 * 使用哨兵   和  不使用哨兵的版本
 * 哨兵的作用，简化边界条件，使得一些边界条件不用被判断。
 *
 * 当可以增加一个判断而减少多个判断时，可以使用哨兵
 *
 *
 */
public class MyCircularQueue {

    private int[] array;

    private int startIndex;

    private int endIndex;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        array = new int[k];
        startIndex = 0;
        endIndex = 0;
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        int tmp = array[endIndex];
        if(!(startIndex == endIndex && tmp == 0)){
            endIndex = nextIndex(endIndex);
        }
        array[endIndex] = value;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if(isEmpty()){
            return  false;
        }
        array[startIndex] = 0;
        startIndex = startIndex == endIndex? startIndex : nextIndex(startIndex);
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if(isEmpty()){
            return  -1;
        }
        return array[startIndex];
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        return array[endIndex];
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return startIndex == endIndex && array[startIndex] == 0;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return startIndex == nextIndex(endIndex);
    }


    private int nextIndex(int curr){
        return (++curr)%array.length;
    }

    private int formerIndex(int curr){
        return curr == 0? array.length - 1:--curr;
    }

}

